package algorithm.dynamic_programming;


public class PalindromeSubsequence {
    //范围尝试模型在乎讨论开头如何和结尾如何
    //样本对应模型在乎讨论两个样本的结尾如何

    public static int lpsl(String s){
        if(s == null || s.length() == 0)
            return 0;
        return process(s.toCharArray(), 0, s.length() - 1);
    }

    public static int process(char[] s, int left, int right){
        if(left == right)
            return 1;
        if(left + 1 == right)
            return s[left] == s[right]? 2 : 1;
        int max =Math.max(process(s, left + 1, right), process(s, left, right - 1));
        if(s[left] == s[right]){
            int process = process(s, left + 1, right - 1) + 2;
            return Math.max(max, process);
        }
        return max;
    }

    public static int lpsl2(String s){
        if(s == null || s.length() == 0){
            return 0;
        }
        char[] chars = s.toCharArray();
        int[][] dp = new int[chars.length][chars.length];
        for (int i = 0; i < chars.length; i++) {
            dp[i][i] = 1;
            if(i < chars.length - 1)
                dp[i][i + 1] = chars[i] == chars[i + 1]? 2 : 1;
        }
        for (int i = chars.length - 3; i >= 0; i--) {
            for (int j = i + 2; j < chars.length; j++) {
                int max = Math.max(dp[i + 1][j], dp[i][j - 1]);
                if(chars[i] == chars[j]){
                    dp[i][j] = Math.max(max, dp[i + 1][j - 1] + 2);
                }else
                    dp[i][j] = max;
            }
        }
        return dp[0][chars.length - 1];
    }

}
